package leetcode;

import java.awt.image.ImageProducer;
import java.util.HashMap;
import java.util.LinkedList;

public class Lc909 {
    public int n ;
    public int end;
    HashMap<Integer, int[]> location;

    public int snakesAndLadders(int[][] board) {
        location = new HashMap<>();
        int n = board.length;
        int end = n * n;
        int cnt = 0, y = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (y == 0) {
                while (y < n) {
                    location.put(++cnt,new int[]{i, y});
                    y ++;
                }
                y = n - 1;
            }else {
                while (y >= 0) {
                    location.put(++cnt, new int[]{i, y});
                    y--;
                }
                y = 0;
            }
        }
        boolean[] visited = new boolean[end + 1];
        LinkedList<int[]> queue = new LinkedList<>(); //queue队列保存位置编号 和 到当前位置的步数
        queue.offer(new int[]{1, 0}); //初始位置编号1，步数0
        visited[1] = true;
        while (!queue.isEmpty()) {
            int curId = queue.peek()[0];
            int curStep = queue.poll()[1];
            for (int i = 1; i < 7; i++) {
                int nId = curId + i;
//                if (nId == end) return curStep + 1;
                if (nId > end) break;
                if (visited[nId]) continue;
                int nx = location.get(nId)[0];
                int ny = location.get(nId)[1];
                if (board[nx][ny] != -1) { // 有蛇或梯子，就爬过去到新的位置
                    visited[curId] = true;
                    nId = board[nx][ny];
                }
                if (visited[nId]) continue;
                if (nId == end) return curStep + 1;
                queue.offer(new int[]{nId, curStep + 1});
                visited[nId] = true;
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        Lc909 lc909 = new Lc909();
//        int[][] b ={{-1,-1,-1,-1,-1,-1},
//                    {-1,-1,-1,-1,-1,-1},
//                    {-1,-1,-1,-1,-1,-1},
//                    {-1,35,-1,-1,13,-1},
//                    {-1,-1,-1,-1,-1,-1},
//                    {-1,15,-1,-1,-1,-1}};
////
//        int[][] b = {{-1,-1,2,21,-1},
//                {16,-1,24,-1,4},
//                {2,3,-1,-1,-1},
//                {-1,11,23,18,-1},
//                {-1,-1,-1,23,-1}};

//        int[][] b = {{-1,-1,-1},{-1,9,8},{-1,8,9}};
        int[][] b = {{1,1,-1},{1,1,1},{-1,1,1}};



        System.out.println(lc909.snakesAndLadders(b));
    }

}
